# 反转链表： https://leetcode-cn.com/problems/reverse-linked-list/submissions/


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 最开始的写法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        """ 我的想法是采用 设立首元结点，采用头插法，逆序链表 """
        cur = ListNode(0)
        p = head
        while p:
            # p 用来遍历链表， node 作为一个节点，使用头插法插入新链表
            node = p
            if cur.next is None:
                cur.next = node
                p = p.next
                # 一定置None, 否则会出现环
                node.next = None
            else:
                temp = cur.next
                cur.next = node
                p = p.next
                node.next = temp

        head =  cur.next      
        return head



# 优化后发现不需要区分     
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        """ 我的想法是采用 设立首元结点，采用头插法，逆序链表 """
        cur = ListNode(0)
        p = head
        while p:
            # p 用来遍历链表， node 作为一个节点(指针置为 None，不连接其他)，使用头插法插入新链表
            # 1. 得到节点， p指向下一位
            node = p
            p = p.next
            node.next = None
            
            # 2. 进行插入
            temp = cur.next
            cur.next = node
            node.next = temp

        head =  cur.next      
        return head


# 另外的写法： 迭代法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        """ 还有一种方法，不需要使用首元结点 
            1 -> 2 -> 3 -> 4    可以依次逆序每个指针
            1 <- 2 <- 3 <- 4    4变为了新的表头
            和头插法一样， 需要注意改变节点指针的时候，不能影响到 遍历下一个元素
        """
        # 1. 首先需要一个指针p顺序遍历节点， 还需要pre 和 cur 指针用于反转
        pre = None
        p = cur = head
        while p:
            # 1. 更新cur为当前节点
            cur = p
            # 2. p指针后移
            p = p.next
            # 3. 做反转
            cur.next = pre
            # 4. 更新pre为当前节点
            pre = cur

        # 5. 重新定义 head指向链表末尾
        head = cur
        return head


# 还可以 以递归的形式解决问题
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        """ 
            迭代解法中，每一步都是 重新指向next指针， 可以分治法，使用递归求解。找到最小子问题及终止条件
            需要调用递归栈， 空间效率要低很多。
        """
        # 1. 首先需要一个指针p顺序遍历节点， 还需要pre 和 cur 指针用于反转
        def reverse(pre, cur):
            # 当cur为None了， 说明pre指向最后的节点，返回作为新的头结点
            if not cur: 
                return pre
            next = cur.next
            cur.next = pre
            return reverse(cur, next)
        

        head = reverse(None, head)
        return head